package day_2022_7_to_8.day48;

import java.util.*;

/**
 * 全排列2
 * @author haomin
 * @date 2022/07/16 10:53
 **/
public class Day2_2_Num47_PermuteUnique {
    public List<List<Integer>> result = new LinkedList<>();
    public List<Integer> ret = new LinkedList<>();

    public List<List<Integer>> permuteUnique(int[] nums) {
        // 定义一个变量表示该节点是否被访问 0：未访问 1：已访问
        int[] used = new int[nums.length];
        dfs(nums,0,nums.length,used);
        return result;
    }

    public void dfs(int[] nums, int left, int right, int[] used){
        if(ret.size() == right){        // 搜索到一个解，添加到result
            if(!result.contains(new LinkedList<>(ret)))   // 去重
            result.add(new LinkedList<>(ret));
        }
        for(int i = 0;i < right;i++){   // 还未回溯到头
            // 未访问数字才能排列
            if(used[i] == 0){
                ret.add(nums[i]);used[i] = 1;
                dfs(nums,left,right, used);   // 扩展下一个结点
                ret.remove(ret.size()-1);used[i] = 0;
            }
        }
    }
}